#ifndef __CAPAINDICES_ARBOLBMAS_ESTRATEGIAINSERCION_CPP
#define __CAPAINDICES_ARBOLBMAS_ESTRATEGIAINSERCION_CPP

/*****************************************************************************
*                     Organizaci�n de Datos - 75.06                          *
*                         C�tedra Lic. Servetto                              *
*            Facultad de Ingenier�a - Universidad de Buenos Aires            *
******************************************************************************/

#include "ArbolBMas.h"
#include <sstream>
#include <iostream>
#include <cmath>

using namespace std;
using namespace Comun;

namespace CapaIndices
{
	EstrategiaInsercion::EstrategiaInsercion(CapaIndices::ArbolBMas *arbol):Estrategia(arbol, false){
		Sobreescribir = false;
	}

	EstrategiaInsercion::~EstrategiaInsercion(){
	}

	string ObtenerIdAnterior(Nodo* padre){

		string idAnterior = "-2";
		for (IteradorDeRegistros reg = padre->Registros.begin();reg != padre->Registros.end(); reg++)
			{
				if ((*reg).Marcado)					
					break;												
				else
				{
					for (IteradorDeAtributos a = reg->Atributos.begin(); a!= reg->Atributos.end(); a++)
						if ((*a).Nombre == "HijoDerecho")
							idAnterior = (*a).Valor;
				}
			}		

			stringstream* s = new stringstream();

			if (idAnterior == "-2")
			{
				*s << padre->HijoIzquierdo;
				idAnterior = s->str();
			}
			return idAnterior;
	}


	string ObtenerIdSiguiente(string idAnterior, ArbolBMas* arbol, int grupoId){
		
		string idSiguiente;
		Grupo anterior = arbol->ArchivoDatos->LeerGrupo(atoi(idAnterior.c_str()));

		for (IteradorDeAtributos a = anterior.Atributos.begin();a != anterior.Atributos.end();a++)
		{
			if ((*a).Nombre == "NodoSiguiente")
			{
				stringstream s;
				s << grupoId;

				idSiguiente = (*a).Valor; 
				(*a).Valor = s.str();
			}
		}

		arbol->ArchivoDatos->GuardarGrupo(anterior,true);

		return idSiguiente;
	}

	void ActualizarAnteriorEnSiguiente(string idSiguiente, ArbolBMas* arbol, int grupoId){
		Grupo siguiente = arbol->ArchivoDatos->LeerGrupo(atoi(idSiguiente.c_str()));
		for (IteradorDeAtributos a = siguiente.Atributos.begin();a != siguiente.Atributos.end();a++)
		{
			if ((*a).Nombre == "NodoAnterior")
			{
				stringstream s;
				s<< grupoId;

				(*a).Valor = s.str();
			}
		}
		arbol->ArchivoDatos->GuardarGrupo(siguiente,true);
	}

	int CalcaularTamanioParticion(int ponderado, int total, Grupo* grupo)
	{
		div_t media = div(ponderado,total);
		int tamideal = media.quot;

		if ( ( media.rem > (total*.5) ) && ( tamideal < grupo->Registros.size() - 1 ) )
		{
			int contAux = 1, tamanioUno = 0, tamanioDos = 0, tamanioConflicto = 0;
			bool primero = true;

			for (IteradorDeRegistros i=grupo->Registros.begin(); i!=grupo->Registros.end();i++)
			{
				if (contAux < tamideal)				
					tamanioUno += (*i).Tamanio;				
				else if (contAux == tamideal)				
					tamanioUno += (*i).Tamanio;						
				else
				{
					if(primero)
					{
						tamanioConflicto = (*i).Tamanio;
						primero = false;
					}
					tamanioDos += (*i).Tamanio;
				}
				contAux++;
			}

			if (abs(tamanioUno-tamanioDos) > abs((tamanioUno+tamanioConflicto)-(tamanioDos - tamanioConflicto)))
				tamideal++;
		}

		return tamideal;
	}

	Registro* ObtenerOrientador(list<MetadatosAtributo> claves, list<Atributo> datos)
	{
		Registro* r = new Registro();

		for (IteradorDeMetadatosAtributos i = claves.begin(); i!= claves.end(); i++)
		{
			for (IteradorDeAtributos j = datos.begin(); j!= datos.end(); j++)
				if ((*j).Nombre == (*i).Nombre)
				{
					Atributo a((*j).Nombre,(*j).Valor);
					a.Tipo = (*j).Tipo;
					r->Atributos.push_back(a);
				}
		}

		return r;
	}

	Atributo* CrearAtributo(string nombre, string valor, TipoRegistro tipo)
	{
		Atributo* a = new Atributo(nombre,valor);
		a->Tipo = tipo;
		return a;
	}

	Atributo* CrearAtributo(string nombre, int valor, TipoRegistro tipo)
	{
		stringstream* s = new stringstream();
		*s << valor;

		Atributo* a = new Atributo(nombre,s->str());
		a->Tipo = tipo;

		delete s;
		return a;
	}

	Resultado* ResultadoExito()	
	{
		Resultado* r = new Resultado();
		r->Codigo = Exito;
		return r;
	}

	
	void EstrategiaInsercion::PrimerInsercion(Clave* clave)
	{
		Grupo* g=new Grupo();		
		Arbol->ArchivoDatos->CrearGrupo(*g);
		Registro* orientador = ObtenerOrientador(Arbol->Metadata->Claves,clave->DatosAInsertar);	
		Registro* r = new Registro();

		if (Arbol->Metadata->Tipo == Griego)
		{
			// Inserta todos los campos
			for (IteradorDeMetadatosAtributos h1=Arbol->Metadata->CamposRegsitro.begin(); h1!=Arbol->Metadata->CamposRegsitro.end();h1++)
				for (IteradorDeAtributos h2=clave->DatosAInsertar.begin(); h2!=clave->DatosAInsertar.end();h2++)
					if (h1->Nombre == h2->Nombre)
						r->Atributos.insert(r->Atributos.end(),*h2);
		}
		else
		{
			// Inserta todos los campos presentes en la clave primaria
			for (IteradorDeMetadatosAtributos j = Arbol->Metadata->ClavePrimaria.begin(); j!= Arbol->Metadata->ClavePrimaria.end(); j++)
				for (IteradorDeAtributos i = clave->DatosAInsertar.begin(); i!= clave->DatosAInsertar.end(); i++)				
					if ((*i).Nombre == (*j).Nombre)
						r->Atributos.insert(r->Atributos.end(),*i);
		}


		orientador->Atributos.push_back(*CrearAtributo("HijoDerecho",g->GrupoId,EnteroLargo));

		g->Registros.insert(g->Registros.end(),*r);

		
		Nodo* raiz = (* Camino.begin());
		

		raiz->HijoIzquierdo = -1;
		raiz->Registros.insert(raiz->Registros.begin(),*orientador);
		raiz->Contador++;

		g->Atributos.push_back(*CrearAtributo("Cantidad","1",Entero));		
		if (Arbol->Metadata->Tipo == Romano)
			g->Atributos.push_back(*CrearAtributo("NodoAnterior","-1",EnteroLargo));

		g->Atributos.push_back(*CrearAtributo("NodoSiguiente","-1",EnteroLargo));		

		if (Arbol->Metadata->Tipo == Romano)
		{
			g->Atributos.push_back(*CrearAtributo("GrupoDesborde","-1",EnteroLargo));		

			for (IteradorDeMetadatosAtributos atribClave = Arbol->Metadata->Claves.begin(); atribClave != Arbol->Metadata->Claves.end(); atribClave++)			
			{
				for (IteradorDeAtributos valor = clave->DatosAInsertar.begin(); valor != clave->DatosAInsertar.end(); valor++)
					if (atribClave->Nombre == valor->Nombre)
					{
						g->Atributos.push_back(*CrearAtributo(valor->Nombre,valor->Valor,valor->Tipo));
					}	
			}
		}

		if (Arbol->Metadata->Tipo == Griego)
		{
			Grupo* hijoIzq = new Grupo();

			g->Atributos.push_back(*CrearAtributo("NodoAnterior",hijoIzq->GrupoId,EnteroLargo));

			Arbol->ArchivoDatos->CrearGrupo(*hijoIzq);		
			raiz->HijoIzquierdo = hijoIzq->GrupoId;

			hijoIzq->Atributos.push_back(*CrearAtributo("Cantidad","0",Entero));		
			hijoIzq->Atributos.push_back(*CrearAtributo("NodoAnterior","-1",EnteroLargo));
			hijoIzq->Atributos.push_back(*CrearAtributo("NodoSiguiente", g->GrupoId,EnteroLargo));

			CodigoResultado resInsercion2 = Arbol->ArchivoDatos->GuardarGrupo(*hijoIzq,true);				

			if (resInsercion2 == 1)
			{
				cerr << "CapaIndices->ArbolBMas->Estrategias->EstrategiaInsercion.cpp->EstrategiaInsercion::PrimerInsercion(Clave* clave)" << endl << "El tamanio del registro excede el tama�o del grupo." << endl;
				throw new exception();
			}
		}
				

		CodigoResultado resInsercion = Arbol->ArchivoDatos->GuardarGrupo(*g,true);		
		
		if (resInsercion == 1)
		{
			cerr << "CapaIndices->ArbolBMas->Estrategias->EstrategiaInsercion.cpp->EstrategiaInsercion::PrimerInsercion(Clave* clave)" << endl << "El tamanio del registro excede el tama�o del grupo." << endl;
			throw new exception();
		}
		
		
		Arbol->ActualizarNodo(&raiz,true);
	}

	
	Resultado* EstrategiaInsercion::InsercionPolivalente(Nodo* nodo, Clave* clave){

		CondicionMayor* mayor = new CondicionMayor();
		Registro* regainsertar = new Registro();
		IteradorDeRegistros puntero;

		bool hallado = false;

		for (IteradorDeRegistros i=nodo->Registros.begin() ;i!=nodo->Registros.end(); i++){

			if (mayor->Analizar(*ExtraerAtributosClave(&((*i).Atributos),Arbol->Metadata->Claves),clave->ValoresBusqueda)){
				puntero = i;
				hallado = true;
				break;
			}
		}

		if (!hallado)
			puntero = nodo->Registros.end();			

		//armo el registro con los atributos que tengo que insertar

		for (IteradorDeMetadatosAtributos h1=Arbol->Metadata->CamposRegsitro.begin(); h1!=Arbol->Metadata->CamposRegsitro.end();h1++)
			for (IteradorDeAtributos h2=clave->DatosAInsertar.begin(); h2!=clave->DatosAInsertar.end();h2++)
				if (h1->Nombre == h2->Nombre)
					regainsertar->Atributos.insert(regainsertar->Atributos.end(),*h2);

		//inserto el registro nuevo en el nuevo grupo
		nodo->Registros.insert(puntero,*regainsertar);
		nodo->Contador++;

		nodo->Sincronizar(true);


		//guardo el grupo con los datos ya insertados
		CodigoResultado r = Arbol->ArchivoDatos->GuardarGrupo(*nodo,true);

		Resultado* res = new Resultado();
		res->Codigo =r;
		return res;
	}

	
	Resultado* EstrategiaInsercion::InsercionMonovalente(Nodo* nodo, Clave* clave){
		// Crea un nuevo orientador para la lista
		Registro* orientador = ObtenerOrientador(Arbol->Metadata->Claves,clave->DatosAInsertar);

		// Crea una nueva lista de referencias al indice primario
		Grupo* g=new Grupo();
		Arbol->ArchivoDatos->CrearGrupo(*g);

		orientador->Atributos.push_back(*CrearAtributo("HijoDerecho",g->GrupoId,EnteroLargo));	

		// Crea una referencia al Indice Primario
		Registro* registroDatos = new Registro();

		for (IteradorDeMetadatosAtributos h1=Arbol->Metadata->CamposRegsitro.begin(); h1!=Arbol->Metadata->CamposRegsitro.end();h1++)
			for (IteradorDeAtributos h2=clave->DatosAInsertar.begin(); h2!=clave->DatosAInsertar.end();h2++)
				if (h1->Nombre == h2->Nombre)
					registroDatos->Atributos.push_back(*h2);

		g->Registros.push_back(*registroDatos);

		Nodo* padre = *--Camino.end();

		string idSiguiente = "-1";
		string idAnterior = ObtenerIdAnterior(padre);
		

		if (idAnterior != "-1")		
			idSiguiente = ObtenerIdSiguiente(idAnterior,Arbol,g->GrupoId);		

		if (idSiguiente != "-1")
			ActualizarAnteriorEnSiguiente(idSiguiente,Arbol,g->GrupoId);

		
		g->Atributos.push_back(*CrearAtributo("Cantidad","1",Entero));		
		g->Atributos.push_back(*CrearAtributo("NodoAnterior", idAnterior,EnteroLargo));
		g->Atributos.push_back(*CrearAtributo("NodoSiguiente", idSiguiente,EnteroLargo));		

		CodigoResultado resInsercion = Arbol->ArchivoDatos->GuardarGrupo(*g,true);
		
		if (resInsercion == 1)
		{
			cerr << "CapaIndices->ArbolBMas->Estrategias->EstrategiaInsercion.cpp->EstrategiaInsercion::InsercionMonovalente(Nodo* nodo, Clave* clave)" << endl << "El tamanio del registro excede el tama�o del grupo." << endl;
			throw new exception();
		}

		return &InsertarEnIndice(--Camino.end(),orientador);
	}	

	
	Resultado* EstrategiaInsercion::InsercionSecundario(Nodo* nodo, Clave* clave, bool existe, bool desborde){

		Registro* regainsertar = new Registro();
		IteradorDeRegistros puntero = nodo->Registros.begin();

		if (existe)
		{
			for (IteradorDeMetadatosAtributos j = Arbol->Metadata->ClavePrimaria.begin(); j!= Arbol->Metadata->ClavePrimaria.end(); j++)
				for (IteradorDeAtributos h=clave->DatosAInsertar.begin(); h!=clave->DatosAInsertar.end();h++)				
					if ((*h).Nombre == (*j).Nombre)
						regainsertar->Atributos.insert(regainsertar->Atributos.end(),*h);	

			//inserto el registro nuevo en el nuevo grupo
			nodo->Registros.insert(nodo->Registros.end(),*regainsertar);
			nodo->Contador++;

			nodo->Sincronizar(true);
			//guardo el grupo con los datos ya insertados
			CodigoResultado r = Arbol->ArchivoDatos->GuardarGrupo(*nodo,true);

			Resultado* res = new Resultado();
			res->Codigo =r;
			return res;
		}
		else
		{
			// Crea un nuevo orientador para la lista
			Registro* orientador = ObtenerOrientador(Arbol->Metadata->Claves,clave->DatosAInsertar);

			// Crea una nueva lista de referencias al indice primario
			Grupo* g=new Grupo();
			Arbol->ArchivoDatos->CrearGrupo(*g);

			orientador->Atributos.push_back(*CrearAtributo("HijoDerecho",g->GrupoId,EnteroLargo));

			// Crea una referencia al Indice Primario
			Registro* referenciaPrimaria = new Registro();

			for (IteradorDeMetadatosAtributos j = Arbol->Metadata->ClavePrimaria.begin(); j!= Arbol->Metadata->ClavePrimaria.end(); j++)
				for (IteradorDeAtributos i = clave->DatosAInsertar.begin(); i!= clave->DatosAInsertar.end(); i++)				
					if ((*i).Nombre == (*j).Nombre)
						referenciaPrimaria->Atributos.insert(referenciaPrimaria->Atributos.end(),*i);

			g->Registros.insert(g->Registros.end(),*referenciaPrimaria);

			Nodo* padre = *--Camino.end();

				
			string idSiguiente = "-1";
			string idAnterior = ObtenerIdAnterior(padre);			
			
			if (idAnterior != "-1")
				idSiguiente = ObtenerIdSiguiente(idAnterior,Arbol,g->GrupoId);			

			if (idSiguiente != "-1")
				ActualizarAnteriorEnSiguiente(idSiguiente,Arbol,g->GrupoId);

			g->Atributos.push_back(*CrearAtributo("Cantidad","1",Entero));		
			g->Atributos.push_back(*CrearAtributo("NodoAnterior", idAnterior,EnteroLargo));
			g->Atributos.push_back(*CrearAtributo("NodoSiguiente", idSiguiente,EnteroLargo));			
			g->Atributos.push_back(*CrearAtributo("GrupoDesborde", "-1",EnteroLargo));

			for (IteradorDeMetadatosAtributos atribClave = Arbol->Metadata->Claves.begin(); atribClave != Arbol->Metadata->Claves.end(); atribClave++)			
			{
				for (IteradorDeAtributos valor = clave->DatosAInsertar.begin(); valor != clave->DatosAInsertar.end(); valor++)
					if (atribClave->Nombre == valor->Nombre)
					{
						g->Atributos.push_back(*CrearAtributo(valor->Nombre,valor->Valor,valor->Tipo));
					}	
			}

			if (desborde)
			{
				nodo->GrupoDesborde = g->GrupoId;
				Arbol->ArchivoDatos->GuardarGrupo(*g,true);
				Arbol->ActualizarNodo(&nodo,true);

				return ResultadoExito();
			}

			Arbol->ArchivoDatos->GuardarGrupo(*g,true);
			return &InsertarEnIndice(--Camino.end(),orientador);
		}
	}

	
	Resultado* EstrategiaInsercion::ResolverSobreflujoPolivalente(Grupo* grupo2,CodigoResultado res2)
	{
		Registro primero = *grupo2->Registros.begin();
		Resultado res;		

		//generelo el registro que voy a insertar en el nodo
		stringstream* stream = new stringstream();
		*stream << grupo2->GrupoId;

		Atributo* at2= new Atributo("HijoDerecho",stream->str());
		at2->Tipo = EnteroLargo;
		Registro* reg = new Registro();
		list<Atributo>* listAux = ExtraerAtributosClave(&(primero.Atributos),Arbol->Metadata->Claves);

		for (IteradorDeAtributos i = listAux->begin();i!=listAux->end();i++)
			reg->Atributos.insert(reg->Atributos.end(),*i);

		delete listAux;

		reg->Atributos.insert (reg->Atributos.end(),*at2);		
		Resultado resGral=InsertarEnIndice(--(--Camino.end()),reg);

		if (res2 == Sobreflujo){
			Grupo grupo3 = PartirGrupo(grupo2);
			this->Arbol->ArchivoDatos->GuardarGrupo(grupo3,true);

			Registro primero = *grupo3.Registros.begin();
			Resultado res;		

			//generelo el registro que voy a insertar en el nodo
			stringstream* stream = new stringstream();
			*stream << grupo3.GrupoId;

			Atributo* at2= new Atributo("HijoDerecho",stream->str());
			at2->Tipo = EnteroLargo;
			Registro* reg = new Registro();
			list<Atributo>* listAux = ExtraerAtributosClave(&(primero.Atributos),Arbol->Metadata->Claves);

			for (IteradorDeAtributos i = listAux->begin();i!=listAux->end();i++)
				reg->Atributos.insert(reg->Atributos.end(),*i);

			delete listAux;

			reg->Atributos.insert (reg->Atributos.end(),*at2);
			
			return &InsertarEnIndice(--(--Camino.end()),reg);

		}else
		{
			return ResultadoExito();
		}
	}

	
	Resultado EstrategiaInsercion::EjecutarEstrategia(CapaIndices::Clave *clave){

		Resultado  res;
		Resultado existe=LocalizarClave(clave);
		//ClaveValor auxclave;

		// Significa que no existe nigun grupo de datos creado
		if (Camino.size() == 1)
		{
			if ( (* Camino.begin())->Contador == 0)
			{
				PrimerInsercion(clave);
				return *ResultadoExito();
			}
		}

		//inserto solo si la clave existe pero esta activado sobreescribir o si la clave no existe
		if ( ( (existe.Codigo== Exito) && ( (this->Sobreescribir) || (Arbol->Metadata->Tipo == Romano) )  ) || (existe.Codigo == ClaveNoEncontrada)){

			//nodo donde se encuentra el id del grupo en donde debo insertar
			Nodo* nodo = (*--Camino.end());
			nodo->Sincronizar(true);
			Registro* regainsertar = new Registro();
			IteradorDeRegistros puntero = nodo->Registros.begin();
			Resultado* r = new Resultado();

			if (Arbol->Metadata->Tipo == Griego)
			{
				if (Arbol->Metadata->TipoDato == Polivalente)				
					r = InsercionPolivalente(nodo,clave);				
				else				
					r = InsercionMonovalente(nodo,clave);				
			}
			else
			{
				r = InsercionSecundario(nodo,clave,existe.Codigo == Exito,false);
			}

			if (r->Codigo == Exito)	
			{
				//si lo grab� bien no tengo que hacer mas nada
				res.mensaje = "El Registro fue ingresado con exito";
				clave->RegistrosAfectados++;
			}
			else if (r->Codigo == Error)
			{
				res.mensaje = "Se produjo un error desconocido al intentar actualizar el archivo ";
			}
			else if (r->Codigo == Sobreflujo)
			{
				if (Arbol->Metadata->Tipo == Griego)
				{
					nodo->Contador--;
					Grupo grupo2=PartirGrupo(nodo);

					CodigoResultado res2 = this->Arbol->ArchivoDatos->GuardarGrupo(grupo2,true);

					//Si no lo puedo insertar es porque el Registro original es mas grande que el tama�o que
					//un grupo,entonces debo dar error (no puede dar sobreflujo)
					if ( (res.Codigo!=Error) && (res2 != Error))					
						return *ResolverSobreflujoPolivalente(&grupo2,res2);					
				}
				else
					return *InsercionSecundario(nodo,clave,false,true);
				
			}
		}
		else
		{
			res.Codigo=Error;
			res.mensaje="El registro no pudo ser insertado porque ya existe en el indice";
		}

		return res;
	}


	
	//actualiza los nodos con el nuevo valor del IDGrupo	
	Resultado EstrategiaInsercion::InsertarEnIndice(IteradorDePunterosANodo iterador, Registro* orientador){

		Resultado* resultado = new Resultado();
		bool hoja = true;
		Nodo* nodo = (* iterador);
		CodigoResultado cres = InsertarEnNodo(nodo,*orientador);

		do {
			if (cres == Exito)
			{
				resultado->mensaje ="El Nodo ha sido actualizado con exito";
			}
			else if (cres == Error)
			{
				resultado->mensaje = "Se produjo un error desconocido al intentar actualizar el nodo en el archivo indice";
			}
			else if (cres == Sobreflujo)
			{
				if ( nodo->NodoId != (* Camino.begin())->NodoId )
				{
					//entonces es nodo raiz y debo crear un nuevo nodo
					Registro* regaelevar =NULL;

					if (hoja)
					{
						regaelevar = PartirNodo(nodo,Hoja);
						hoja = false;
					}
					else
						regaelevar = PartirNodo(nodo,Interno);

					//this->Arbol->ActualizarNodo(&nuevoNodo,true);

					// Apunto al nuevo registro a insertar, esta vez en el padre
					nodo = (*--iterador);
					cres=InsertarEnNodo(nodo,*regaelevar);
				}
				else
				{
					//parto el nodo raiz y creo uno nuevo

					Nodo* nuevoNodoAux =new Nodo();

					Registro* regaelevar;
					if (hoja)
					{
						this->Arbol->CrearNodo(Hoja,&nuevoNodoAux);
						regaelevar = PartirNodo(nodo,Hoja);
						nodo->Tipo = Interno;
						hoja = false;
					}
					else
					{
						regaelevar = PartirNodo(nodo,Interno);
						this->Arbol->CrearNodo(Interno,&nuevoNodoAux);
					}

					nuevoNodoAux->HijoIzquierdo = nodo->HijoIzquierdo;
					nodo->HijoIzquierdo = nuevoNodoAux->NodoId;

					nuevoNodoAux->Contador = nodo->Contador;

					nodo->Contador = 1;

					nuevoNodoAux->Atributos.clear();

					// Copio Todo al auxiliar para mantener la raiz en el nodo 0
					for (IteradorDeAtributos a = nodo->Atributos.begin(); a!=nodo->Atributos.end(); a++)
						nuevoNodoAux->Atributos.insert(nuevoNodoAux->Atributos.end(),(* a));

					nodo->Atributos.clear();

					for (IteradorDeRegistros r = nodo->Registros.begin(); r!=nodo->Registros.end(); r++)
						nuevoNodoAux->Registros.insert(nuevoNodoAux->Registros.end(),*r);

					nodo->Registros.clear();

					// Obtiene el orientador para insertar en el nuevo nodo Raiz
					//Registro regaelevar=SepararPrimerRegistro(nuevonodo);
					// Guarda los nodos
					//this->Arbol->ActualizarNodo(&nuevonodo,true);

					nodo->Registros.insert(nodo->Registros.end(),*regaelevar);
					this->Arbol->ActualizarNodo(&nodo,true);
					this->Arbol->ActualizarNodo(&nuevoNodoAux,true);

					cres = Exito;
				}
			}
		}
		while(cres == Sobreflujo);

		resultado->Codigo = cres;
		return *resultado;
	}

	
	Registro* EstrategiaInsercion::PartirNodo(Nodo* nodo, TipoNodo tipo){
		
		if( ( nodo->Registros.size() == 2 ) )
		{
			cerr << "CapaIndices->EstrategiaInsercion.cpp->EstrategiaInsercion::PartirNodo(Nodo* nodo, TipoNodo tipo)" << endl << "El Nodo a partir solo posee dos registros. Imposible particionar." << endl;
			throw new exception();
		}
		
		Nodo* nuevonodo=new Nodo();
		Arbol->CrearNodo(tipo,&nuevonodo);
		int indicePonderado = 0;
		int tamanioTotal = 0;
		int contador =1;


		for (IteradorDeRegistros i=nodo->Registros.begin(); i!=nodo->Registros.end();i++){
			indicePonderado += contador*(* i).Tamanio;
			tamanioTotal += (* i).Tamanio;
			contador++;
		}

		int tamideal = CalcaularTamanioParticion(indicePonderado,tamanioTotal,nodo);
		int size = nodo->Registros.size()-tamideal;

		if (size == 1)
		{
			tamideal--;
			size++;
		}
		else if (size == 0)
		{
			tamideal-=2;
			size+=2;
		}

		Registro** arrayAux = new Registro*[size];
		int i=0;

		contador = 0;
		for (IteradorDeRegistros puntero=nodo->Registros.begin(); puntero!=nodo->Registros.end();puntero++){
			if (contador>=tamideal){
				if (nuevonodo->Registros.empty()){
					nuevonodo->Registros.insert(nuevonodo->Registros.end(),*puntero);
					nuevonodo->HijoIzquierdo=BuscarHijoIzq(*nodo,*puntero);
				} else {
					nuevonodo->Registros.insert(nuevonodo->Registros.end(),*puntero);
				}
				arrayAux[i++] = &(* puntero);
			}
			contador++;
		}

		for (int i = 0; i< size; i++)
			nodo->Registros.remove(*arrayAux[i]);

		nodo->Contador = size;
		nuevonodo->Contador = tamideal;			

		Registro* regAElevar = SepararPrimerRegistro(nuevonodo);

		/*if( ( nodo->Registros.size() == 0 ) || ( nuevonodo->Registros.size() == 0 ) )
		{
			cerr << "CapaIndices->EstrategiaInsercion.cpp->EstrategiaInsercion::PartirNodo(Nodo* nodo, TipoNodo tipo)" << endl << "El Nodo a partir solo posee dos nodos. Imposible particionar." << endl;
			throw new exception();
		}*/

		
		this->Arbol->ActualizarNodo(&nodo,true);
		this->Arbol->ActualizarNodo(&nuevonodo,true);

		return regAElevar;
	}



	
	//inserta el 1 registro de nodo interno en un nodo
	CodigoResultado EstrategiaInsercion::InsertarEnNodo(Nodo* nodo,Registro reg){
		bool insertado=false;

		//siempre el nodo va a tener algun dato, porque cuando se crea se hace con un dato
		//creo el registro que contiene los datos que debo insertar en el nodo
		for (IteradorDeRegistros i=nodo->Registros.begin(); (i!=nodo->Registros.end()) && !insertado ;i++){
			if ((*i).Marcado){
				nodo->Registros.insert(i,reg);
				insertado=true;
			}
		}

		if (!insertado)
			nodo->Registros.insert(nodo->Registros.end(),reg);

		nodo->Contador++;
		Resultado cres= this->Arbol->ActualizarNodo(&nodo,true);
		return cres.Codigo;
	}	
	
	//Parte el grupo en 2 grupos
	//La parte Izquierda queda en "Grupo" y la parte derecha queda en "nuevoGrupo"
	//La parte izquierda se graba autom�ticamente y devuelve el nuevo grupo
	Grupo EstrategiaInsercion::PartirGrupo(Grupo* grupo){

		Grupo* nuevoGrupo = new Grupo();
		int nuevoIDGrupo = this->Arbol->ArchivoDatos->CrearGrupo(*nuevoGrupo);

		nuevoGrupo->GrupoId = nuevoIDGrupo; 
		
		//Le asigno el nuevo IDGrupo que me dio la Capa Fisica al crear el grupo nuevo
		string auxStr;

		for (IteradorDeAtributos i = grupo->Atributos.begin(); i != grupo->Atributos.end(); i++)
		{
			if ((*i).Nombre == "NodoSiguiente")
			{
				auxStr = ((*i).Valor);

				stringstream* ss = new stringstream();
				*ss << nuevoGrupo->GrupoId;
				(*i).Valor = ss->str();

				delete ss;
			}
		}		

		nuevoGrupo->Atributos.push_back(*CrearAtributo("NodoAnterior",grupo->GrupoId,EnteroLargo));
		nuevoGrupo->Atributos.push_back(*CrearAtributo("NodoSiguiente",auxStr,EnteroLargo));

		int indicePonderado = 0;
		int tamanioTotal = 0;
		int contador = 1;

		for (IteradorDeRegistros i=grupo->Registros.begin(); i!=grupo->Registros.end();i++){
			indicePonderado += contador*(* i).Tamanio;
			tamanioTotal += (* i).Tamanio;
			contador++;
		}

		int tamIdeal = CalcaularTamanioParticion(indicePonderado,tamanioTotal,grupo);
		
		contador = 0;

		IteradorDeRegistros aux;
		//Hago Split del Nodoo
		for (IteradorDeRegistros i=grupo->Registros.begin(); i!=grupo->Registros.end();i++, contador++){
			if (contador>=tamIdeal){
				aux = i;
				break;
			}

		}

		int tamanio = grupo->Registros.size()-tamIdeal;

		Registro** arrayAux = new Registro*[tamanio];
		int i=0;

		for (IteradorDeRegistros puntero=aux; puntero!=grupo->Registros.end();puntero++){

			nuevoGrupo->Registros.insert(nuevoGrupo->Registros.end(),*puntero);
			arrayAux[i++] = &(* puntero);
		}

		for (int i = 0; i< tamanio; i++)
			grupo->Registros.remove(*arrayAux[i]);

		nuevoGrupo->Atributos.push_front(*CrearAtributo("Cantidad",tamanio,Entero));

		for (IteradorDeAtributos i = grupo->Atributos.begin();i!=grupo->Atributos.end();i++)
		{
			if ((*i).Nombre == "Cantidad")
			{
				stringstream* ss = new stringstream();
				*ss << tamIdeal;

				(*i).Valor = ss->str();

				delete ss;
			}
		}

		int res10 = this->Arbol->ArchivoDatos->GuardarGrupo(*grupo,true); //siempre va a dar exito

		int sig = atoi(auxStr.c_str());
		if (sig!=-1)
		{
			Grupo derecho = this->Arbol->ArchivoDatos->LeerGrupo(sig);

			for (IteradorDeAtributos i = derecho.Atributos.begin();i!=derecho.Atributos.end();i++)
			{
				if ((*i).Nombre == "NodoAnterior")
				{
					stringstream* ss = new stringstream();
					*ss << nuevoGrupo->GrupoId;

					(*i).Valor = ss->str();					

					delete ss;
				}
			}

			int res11 = this->Arbol->ArchivoDatos->GuardarGrupo(derecho,true);			
		}

		return *nuevoGrupo;
	}

	
	Registro* EstrategiaInsercion::SepararPrimerRegistro(Nodo* nodo){
		Registro* regaentregar=new Registro();
		Registro primero = *nodo->Registros.begin();

		regaentregar->Tamanio = primero.Tamanio;

		for (IteradorDeAtributos i= primero.Atributos.begin();i!= primero.Atributos.end();i++)
			regaentregar->Atributos.insert(regaentregar->Atributos.end(),*i);

		nodo->Registros.remove(*(nodo->Registros.begin()));
		nodo->HijoIzquierdo=atoi((--regaentregar->Atributos.end())->Valor.c_str());
		nodo->Contador--;

		stringstream* s = new stringstream();
		*s << nodo->NodoId;

		(--(regaentregar->Atributos.end()))->Valor = s->str(); //asigno como hijoderecho al nro del nodo

		delete s;

		return regaentregar;

	}
	
	//Busca el id del grupo en donde debo agregar el nuevo registro
	int EstrategiaInsercion::BuscarElGrupo(Nodo nodo, Clave clave){
		int idgrupo;
		bool encontrado=false;
		string aux;
		idgrupo=nodo.HijoIzquierdo;
		IteradorDeRegistros i=nodo.Registros.begin();
		IteradorDeAtributos j;
		do  {
			j=i->Atributos.begin();
			if ((j->Valor) > *(clave.ValoresBusqueda.begin()))
				encontrado=true;
			else{
				aux=(++j)->Valor;
				idgrupo=atoi(aux.c_str());
			}
			i++;
		}while ((i!=nodo.Registros.end()) && (!encontrado));
		//si no lo encontro el id es el hijoderecho del ultimo registro
		if(!encontrado) {
			encontrado=true;
			i=(--nodo.Registros.end());
			j=i->Atributos.begin();
			aux=(++j)->Valor;
			idgrupo=atoi(aux.c_str());
		}
		return idgrupo;
	}

	
	int EstrategiaInsercion::CalcularTamGrupo(Grupo grupo){
		int tamanio=0;
		for(IteradorDeRegistros i = grupo.Registros.begin(); i!=grupo.Registros.end(); i++){
			tamanio=tamanio + i->Tamanio;
		}
		return tamanio;
	}



	
	string EstrategiaInsercion::BuscarClaveDelGrupo(Grupo grupo){
		//me muevo por los registros
		bool encontrado=false;
		string aux="";
		for(IteradorDeRegistros i = grupo.Registros.begin();(i!=grupo.Registros.end())&&(!encontrado);i++){
			//me muevo por los atributos
			for (IteradorDeAtributos j=i->Atributos.begin(); (j!=i->Atributos.end())&&(!encontrado);j++){
				if ((j->Nombre) == (this->Arbol->Metadata->Claves.begin()->Nombre)){
					encontrado=true;
					aux=j->Valor;
				}
			}
		}
		return aux;
	}
	
	//Da el hijo izqueierdo de una clave del nodo (el derecho del registro anterior)
	int EstrategiaInsercion::BuscarHijoIzq(Nodo nodo,Registro RegdelNodo){

		int izq=nodo.HijoIzquierdo;
		bool encontrado=false;


		for(IteradorDeRegistros i = nodo.Registros.begin(); (i!=nodo.Registros.end())&& (!encontrado); i++){
			//for(IteradorDeAtributos j= i->Atributos.begin(); (j!=nodo.Registros.end()) && (!encontrado); j++{
			if (i->Atributos.begin()->Valor ==RegdelNodo.Atributos.begin()->Valor){
				encontrado=true;
			}else{
				izq=atoi((i->Atributos.begin())++->Valor.c_str());
			}
		}
		return izq;

	}


}
#endif
